94

8

Sets and Combinatorics

The Basic Rule of Multiplication

Consider an ordered rr-tuple left parenthesis a 1 comma ellipsis comma a Subscript r Baseline right parenthesis(a1, . . . , ar), in which each member a Subscript iai belongs to a

set with n Subscript ini elements. The total number of possible selections equals n 1 n 2 midline horizontal ellipsis n Subscript r Baselinen1n2 · · · nr; for

example, we select rr balls, one from each of rr boxes, where the iith box contains n Subscript ini

different balls.

8.2.1

Ordered Sampling with Replacement

If all the sets from which successive selections are taken are the same sizenn, the total

number of ordered (distinguishable) selections of rr objects from nn with repetition

(replacement) allowed follows from the multiplication rule

product Underscript i Overscript r Endscripts n Subscript i Baseline equals n Superscript r Baseline period

r∏

i

ni = n^r .

(8.1)

In terms of putting balls in a row of cells, this is equivalent to filling rr consecutive

cells with nn possible choices of balls for each one; after taking a ball from a central

reservoir, it is replenished with an identical ball.

8.2.2

Ordered Sampling Without Replacement

If the balls are not replenished after removal, there are only left parenthesis n minus 1 right parenthesis(n −1) choices of ball

for filling the second cell, left parenthesis n minus 2 right parenthesis(n −2) for the third, and so on. If the number of cells

equals the number of balls (i.e., r equals nr = n), then there are n factorialn! different arrangements—

this is called a permutation (and can be thought of as a bijective mapping of a set

onto itself); more generally, if r less than or equals nr ≤n, the number of arrangements is

Superscript n Baseline upper P Subscript r Baseline equals n left parenthesis n minus 1 right parenthesis midline horizontal ellipsis left parenthesis n minus r plus 1 right parenthesis equals StartFraction n factorial Over left parenthesis n minus r right parenthesis factorial EndFraction commaⁿ Pr = n(n −1) · · · (n −r + 1) =

n!

(n −r)! ^,

(8.2)

remembering that 0 factorial0! is defined as being equal to 1.

Random Choice

This means that all choices are equally probable. For random samples of fixed size, all

possible samples have the same probabilityn Superscript negative rn^−r with replacement and1 divided by upper P Subscript r1/ⁿ Pr without

replacement. The probability of no repetition in a sample is therefore given by the

ratio of these probabilities: Superscript n Baseline upper P Subscript r divided by n Superscript rⁿ Pr/n^r. Criteria for randomness are dealt with in detail

in Chap. 11.